from typing import List


class Solution:
    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
        s1, s2 = len(encoded1), len(encoded2)

        # 将数组中长度坐标改为截止下标
        for i1 in range(1, s1):
            encoded1[i1][1] += encoded1[i1 - 1][1]
        for i2 in range(1, s2):
            encoded2[i2][1] += encoded2[i2 - 1][1]

        # print(encoded1)
        # print(encoded2)

        ans1 = []

        now = 0
        i1, i2 = 0, 0
        while i1 < s1 and i2 < s2:
            v = encoded1[i1][0] * encoded2[i2][0]
            if encoded1[i1][1] < encoded2[i2][1]:
                ans1.append([v, encoded1[i1][1] - now])
                now = encoded1[i1][1]
                i1 += 1
            elif encoded1[i1][1] > encoded2[i2][1]:
                ans1.append([v, encoded2[i2][1] - now])
                now = encoded2[i2][1]
                i2 += 1
            else:  # encoded1[i1][1] == encoded2[i2][1]
                ans1.append([v, encoded1[i1][1] - now])
                now = encoded1[i1][1]
                i1 += 1
                i2 += 1

        ans2 = []
        for v, l in ans1:
            if ans2 and v == ans2[-1][0]:
                ans2[-1][1] += l
            else:
                ans2.append([v, l])

        return ans2


if __name__ == "__main__":
    # [[6,6]]
    print(Solution().findRLEArray(encoded1=[[1, 3], [2, 3]], encoded2=[[6, 3], [3, 3]]))

    # [[2,3],[6,1],[9,2]]
    print(Solution().findRLEArray(encoded1=[[1, 3], [2, 1], [3, 2]], encoded2=[[2, 3], [3, 3]]))

    # 测试用例5/52 : [[2,1],[8,1],[15,3],[25,2],[5,1],[1,4],[10,1],[8,1],[10,3],[12,2],[15,3],[2,1],[1,1],[4,1],[12,1],[8,1],[12,2],[8,1],[6,1],[4,1]]
    print(Solution().findRLEArray(
        encoded1=[[2, 2], [5, 5], [1, 5], [2, 5], [4, 2], [5, 3], [1, 2], [4, 3], [3, 2], [2, 3]],
        encoded2=[[1, 1], [4, 1], [3, 3], [5, 3], [1, 4], [5, 1], [4, 1], [5, 3], [3, 5], [2, 1],
                  [1, 2], [3, 1], [2, 1], [4, 3], [3, 1], [2, 1]]))
